DAY 17 試題

問題描述

給定一個只包含三種類型括號的字串 s，這些括號包括圓括號 ()、方括號 [] 和花括號 {}，要求判斷該字串是否有效。字串是有效的需要滿足以下條件：

1. 左括號必須由相同類型的右括號閉合。
2. 左括號必須按照正確的順序閉合。
3. 每個右括號必須有對應的左括號。

例如：

• 輸入：s = "()"，輸出：true
• 輸入：s = "()[]{}"，輸出：true
• 輸入：s = "(]"，輸出：false
• 輸入：s = "([])"，輸出：true

解題思路

這是一個典型的使用堆疊來解決的問題。堆疊能夠幫助我們追蹤每個開啟的括號，並在遇到閉合括號時檢查是否能夠與最近的開啟括號匹配。具體的步驟如下：

1. 使用堆疊儲存左括號：遍歷字串中的每個字元，如果遇到左括號（(、[、{），則將其放入堆疊。
2. 檢查右括號：如果遇到右括號，則從堆疊中彈出一個元素，檢查是否匹配。如果堆疊為空或括號不匹配，則返回 false。
3. 檢查堆疊：遍歷完成後，如果堆疊為空，則表示括號成對匹配，返回 true；否則返回 false。

class Solution {
public:
    bool isValid(string s) {
        stack<char> stk;
        for (char c : s) {
            if (c == '(' || c == '[' || c == '{') {
                stk.push(c);  // 左括號進入堆疊
            } else {
                if (stk.empty()) return false;  // 沒有對應的左括號
                char top = stk.top();
                stk.pop();
                // 檢查括號是否匹配
                if ((c == ')' && top != '(') ||
                    (c == ']' && top != '[') ||
                    (c == '}' && top != '{')) {
                    return false;
                }
            }
        }
        return stk.empty();  // 檢查堆疊是否為空
    }
};

解法重點與分析

1. 堆疊的應用：堆疊是解決這類括號匹配問題的理想結構。每當遇到左括號時，將其推入堆疊，遇到右括號時，檢查與堆疊頂部的左括號是否匹配。
2. 順序的重要性：必須保證左括號按正確順序閉合，這意味著當檢查到右括號時，它應該匹配最近出現的左括號。
3. 括號匹配的驗證：當遍歷結束時，若堆疊不為空，說明有未閉合的左括號，必然無法形成有效的括號匹配。
4. 時間複雜度：該解法需要遍歷整個字串，因此時間複雜度為 O(n)，其中 n 是字串的長度。
5. 空間複雜度：由於堆疊在最壞情況下需要存儲所有左括號，空間複雜度為 O(n)。

總結

這個問題的關鍵在於如何處理括號匹配和順序檢查。通過堆疊結構，我們可以有效地追蹤左括號並檢查右括號的匹配情況。最終，遍歷完成後，若堆疊為空則括號匹配有效。這種解法的時間複雜度和空間複雜度都為 O(n)，非常適合處理大型輸入。

以上是第十七天的自學內容分享，謝謝大家。